package com.dateConstruction._06_binaryTree;

import com.dateConstruction._04_linkedQueue.SinglyLinkedQueue;
import com.dateConstruction._04_linkedStack.SinglyLinkedStack;
import com.dateConstruction._04_seqQueue.CirSeqQueue;
import com.dateConstruction._04_seqQueue.Queue;
import com.dateConstruction._04_seqStack.SeqStack;

public class BinaryTree<T> implements BinaryTTree<T> {
    
    // 根节点
    public BinaryNode<T> root;
    
    // 构造空二叉树
    public BinaryTree() {
        this.root = null;
    }
    
    // 构造根节点非空的二叉树
    public BinaryTree(T x) {
        this.root = new BinaryNode(x, null, null);
    }
    
    // 判断是否为空二叉树
    public boolean isEmpty() {
        return this.root == null;
    }
    
    
    // 插入x元素作为根节点，x != null，原根结点作为x的左孩子
    public void insert(T x) {
        if (x != null) {
            new BinaryNode<T>(x, this.root, null);
        }
    }

    // 插入x元素作为p结点的左/右孩子，p结点原来的左/右孩子成为x结点的左/右孩子
    public BinaryNode<T> insert(BinaryNode<T> p, T x, boolean left) {
        if (p == null && x == null) {
            return null;
        }
        if (left) {
            return p.left = new  BinaryNode<T>(x, p.left, null);
        } else {
            return p.right = new  BinaryNode<T>(x, null, p.right);
        }
    }
    
    // 删除p结点的左/右子树
    public void remove(BinaryNode<T> p, boolean left) {
        if (p != null) {
            if (left) {
                p.left = null;
            } else {
                p.right = null;
            }
        }
    }
    
    // 清空二叉树
    public void clear() {
        this.root = null;
    }
    
    // 遍历二叉树
    // 先根次序遍历二叉树
    public void preOrder() {
        preOrder(this.root);
        System.out.println();
    }
    // 递归
    public void preOrder(BinaryNode<T> p) {
        if (p != null) {
            System.out.print(p.data + " ");
            preOrder(p.left);
            preOrder(p.right);
        }
    }
    
    // 中根次序遍历二叉树
    public void inOrder() {
        inOrder(this.root);
        System.out.println();
    }
    public void inOrder(BinaryNode<T> p) {
        if (p != null) {
            inOrder(p.left);
            System.out.print(p.data + " ");
            inOrder(p.right);
        }
    }
    
    // 后根次序遍历二叉树
    public void postOrder() {
        postOrder(this.root);
        System.out.println();
    }
    public void postOrder(BinaryNode<T> p) {
        if (p != null) {
            postOrder(p.left);
            postOrder(p.right);
            System.out.print(p.data + " ");
        }
    }
    
    // 根据表明空子树的先根次序构造二叉树
    /*
    
    表明空子树的先根序列为A B D ^ G ^ ^ ^ C E ^ ^ F H ^ ^ ^
    对应二叉树为：
    
             A
           /    \
          B      C
         / ^    / \
        D      E   F 
       ^ \    ^ ^ / ^
          G      H
         ^ ^    ^ ^
    
    对于整体的先根序列：A B D ^ G ^ ^ ^ C E ^ ^ F H ^ ^ ^
    可直接根据遍历规律确定根为A，其左子树为B，B的左子树为D，D的左子树为空，D的左子树确定完了那么，接着确定它的右子树
    确定D的右子树为G，G的左子树为空，G的左子树也确定了，接着确定G的右子树，G的右子树为空，这样G的子树就确定了，
    同时D的子树也确定了，那么B的左子树也确定了，接着确定它的右子树，B的右子树为空，这样B的子树也确定了，也就意味着A的左子树就确定了
    接着确定A的右子树...
    
     */
    public BinaryTree(T[] prelist) {
        this.root = createNode(prelist);
    }
    
    private int i = 0;

    private BinaryNode<T> createNode(T[] prelist) {
        // TODO Auto-generated method stub
        
        // 以从i开始的表明空子树的先根序列，创建一颗以prelist[i]为根的子树，返回子树的根节点
        // 递归算法先创建根节点，再创建左子树，右子树
        BinaryNode<T> root = null;
        if (i < prelist.length) {
            T elem = prelist[i++];
            if (elem != null) {
                root = new BinaryNode<T>(elem, createNode(prelist), createNode(prelist));
            }
        }
        return root;
    }
    
    // 根据未表明空子树的先根和中根次序来构造二叉树（该构造方法不允许存在相同元素）
    /*
    
    先根序列：A B D G C E F H
    中根序列：D G B A E C H F
    首先对于:
    先根序列：A B D G C E F H
    中根序列：D G B A E C H F
    根为A，由中根序列知，左子树为B D G，右子树为C E F H
    然后对于它的左子树：
    先根序列：B D G
    中根序列：D G B
    根为B，由中根序列知，D G均为B的左子树，右子树为空
    然后对于它的左子树：
    先根序列：D G
    中根序列：D G
    根为D，由中根序列知，D的左子树为空，G为D的右子树
    整个A的左子树就确定完了
    然后同理递归确定A的右子树
    
     */
    public BinaryTree(T[] prelist, T[] inlist) {
        this.root = GreateNode(prelist, inlist);
    }

    private BinaryNode<T> GreateNode(T[] prelist, T[] inlist) {
        // TODO Auto-generated method stub
        
        // 处理空树
        if (prelist.length == 0 && inlist.length == 0) {
            return null;
        }
        // 处理叶子树
        if (prelist.length == 1 && inlist.length == 1) {
            BinaryNode<T> root = new BinaryNode<T>(prelist[0], null, null);
            return root;
        }
        
        // System.out.println("prelist = " + Arrays.toString(prelist)); // 过程监控
        // System.out.println("inlist = " + Arrays.toString(inlist));   // 过程监控
        
        // 找到中根序列中根的索引
        int index;
        for (index = 0; index < inlist.length; index++) {
            if (prelist[0].equals(inlist[index])) {
                break;
            }
        }
        
        // System.out.println(index);   // 过程监控
        
        // 从而找到左子树的中根序列为inlist[0]到[index-1]，先根序列为prelist[1]到[index]
        T[] inleft = (T[]) new Object[index];
        T[] preleft = (T[]) new Object[index];
        for (int i = 0; i < index; i++) {
            inleft[i] = inlist[i];
            preleft[i] = prelist[i+1];
        }
        

        
        // 右子树的中根序列为inlist[index+1]到[inlist.length]，先根序列为prelist[index+1]到[prelist.length]
        int len = inlist.length - index - 1;
        if (len < 0) {
            len = 0;
        }
        
        T[] inright = (T[]) new Object[len];
        T[] preright = (T[]) new Object[len];
        for (int i = 0; i < len; i++) {
            inright[i] = inlist[index + i + 1];
            preright[i] = prelist[index + i + 1];
        }
        
        /*
        // 用于过程监控
        System.out.println("preleft = " + Arrays.toString(preleft));
        System.out.println("inleft = " + Arrays.toString(inleft));
        System.out.println("preright = " + Arrays.toString(preright));
        System.out.println("inright = " + Arrays.toString(inright));
        */
        
        // 确定该树的根
        if (prelist.length != 0 && preleft != null && inleft != null && preright != null && inright != null) {
            // System.out.println(prelist[0]);  // 过程监控
            BinaryNode<T> root = new BinaryNode<T>(prelist[0], GreateNode(preleft, inleft), GreateNode(preright, inright));
            return root;
        }
        return null;
    }
    
    // 深拷贝构造二叉树
    public BinaryTree(BinaryTree<T> tree) {
        this.root = createNode(tree.root);
    }
    private BinaryNode<T> createNode(BinaryNode<T> root) {
        // TODO Auto-generated method stub
        if (root == null) {
            return null;
        }
        BinaryNode<T> copyroot = new BinaryNode<T>(root.data, createNode(root.left), createNode(root.right));
        return copyroot;
    }
    
    // 层序遍历二叉树
    public void levelOrder() {
        Queue<BinaryNode<T>> queue = new SinglyLinkedQueue<BinaryNode<T>>();
        queue.add(root);
        while(!queue.isEmpty()) {
            BinaryNode<T> p = queue.poll();
            System.out.print(p.data + " ");
            if (p.left != null) {
                queue.add(p.left);
            }
            if (p.right != null) {
                queue.add(p.right);
            }
        }
        System.out.println();
    }
    
    // 返回以p结点为根的一棵子树的广义表表示字符串，先根次序遍历，递归算法
    public String toGenListString(BinaryNode<T> p) {
        if (p == null) {
            return "^";
        } else if (p.left == null && p.right == null) {
            return p.data.toString();
        } else {
            return p.data.toString() + "(" + toGenListString(p.left) + ", " + toGenListString(p.right) + ")";
        }
    }
    
    // 返回二叉树的广义表表示字符串
    public String toGenListString() {
        return this.toGenListString(this.root);
    }
    
    // 先根次序遍历二叉树的非递归算法
    public void preOrderTraverse() {
        /*
        // 先右入栈再左入栈，实现先左输出后右输出
        SeqStack<BinaryNode<T>> stack = new SeqStack<BinaryNode<T>>();
        stack.push(root);
        while (!stack.isEmpty()) {
            BinaryNode<T> p = stack.pop();
            System.out.print(p.data + " ");
            if (p.right != null) {
                stack.push(p.right);
            }
            if (p.left != null) {
                stack.push(p.left);
            }
        }
        */
        SeqStack<BinaryNode<T>> stack = new SeqStack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                System.out.print(p.data + " ");
                stack.push(p);
                p = p.left;
            } else {
                System.out.print("^ ");
                p = stack.pop();
                p = p.right;
            }
        }
        // 最后一个为null的p没有被输出
        System.out.println("^");
    }
    
    // 返回二叉树的结点数
    public int size() {
        int count = 0;
        SinglyLinkedStack<BinaryNode<T>> stack = new SinglyLinkedStack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                count++;
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
        return count;
    }
    
    // 返回二叉树的高度
    public int height() {
        // TODO Auto-generated method stub
        /*
        // 用双栈实现
        int max = 0;
        int height = 1;
        SeqStack<BinaryNode<T>> stack = new SeqStack<BinaryNode<T>>();
        SeqStack<Integer> heights = new SeqStack<Integer>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                heights.push(height);
                p = p.left;
                height++;
            } else {
                p = stack.pop();
                p = p.right;
                height = heights.pop();
                if (height > max) {
                    max = height;
                }
                height++;
            }
            // System.out.println(stack);
            // System.out.println(heights);
        }
        return max;
        */
        // 用队列实现
        int height = 0;
        CirSeqQueue<BinaryNode<T>> queue = new CirSeqQueue<BinaryNode<T>>(0);
        queue.add(this.root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                BinaryNode<T> p = queue.poll();
                if (p.left != null) {
                    queue.add(p.left);
                }
                if (p.right != null) {
                    queue.add(p.right);
                }
            }
            height++;
        }
        return height;
    }
    
    // 查找并返回首个与key相等元素结点
    public BinaryNode<T> search(T key) {
        // TODO Auto-generated method stub
        CirSeqQueue<BinaryNode<T>> queue = new CirSeqQueue<BinaryNode<T>>(0);
        queue.add(this.root);
        while (!queue.isEmpty()) {
            BinaryNode<T> p = queue.poll();
            if (p.data.equals(key)) {
                return p;
            }
            if (p.left != null) {
                queue.add(p.left);
            }
            if (p.right != null) {
                queue.add(p.right);
            }
        }
        return null;
    }
    
    // 返回首个与key相等元素结点所在层次
    public int level(T key) {
        // TODO Auto-generated method stub
        int height = 0;
        CirSeqQueue<BinaryNode<T>> queue = new CirSeqQueue<BinaryNode<T>>(0);
        queue.add(this.root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                BinaryNode<T> p = queue.poll();
                if (p.data.equals(key)) {
                    return height + 1;
                }
                if (p.left != null) {
                    queue.add(p.left);
                }
                if (p.right != null) {
                    queue.add(p.right);
                }
            }
            height++;
        }
        return -1;
    }
    
    @Override
    // 查找并删除首个以与key相等元素为根的子树
    public void remove(T key) {
        // TODO Auto-generated method stub
        if (key == null) {
            return;
        }
        SeqStack<BinaryNode<T>> stack = new SeqStack<BinaryNode<T>>();
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                if (p.data.equals(key)) {
                    p.left = null;
                    p.right = null;
                    return;
                }
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
    }
    // 返回以层序遍历序列levelList构造完全二叉树
    public static<T> BinaryTree<T> createComplete(T[] levelList) {
        if (levelList == null) {
            return null;
        }
        BinaryTree<T> tree = new BinaryTree<T>();
        int j = 0;
        CirSeqQueue<BinaryNode<T>> queue = new CirSeqQueue<BinaryNode<T>>(0);
        tree.root = new BinaryNode<T>(levelList[j++]);
        queue.add(tree.root);
        BinaryNode<T> p = null;
        while (!queue.isEmpty()) {
            p = queue.poll();
            if (j < levelList.length) {
                p.left = new BinaryNode<T>(levelList[j++]);
                queue.add(p.left);
            }
            if (j < levelList.length) {
                p.right = new BinaryNode<T>(levelList[j++]);
                queue.add(p.right);
            }
        }
        return tree;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("测试BinaryTree(T x)：");
        // 构建只有一个根结点的树bt1
        BinaryTree<String> bt1 = new BinaryTree<String>("A");
        // 添加元素
        bt1.insert(bt1.root, "B", true);
        bt1.insert(bt1.root, "C", false);
        bt1.insert(bt1.root.left, "D", true);
        bt1.insert(bt1.root.right, "E", true);
        bt1.insert(bt1.root.right, "F", false);
        bt1.insert(bt1.root.left.left, "G", false);
        bt1.insert(bt1.root.right.right, "H", true);
        // 先序中序后序遍历二叉树
        System.out.println("bt1先根遍历：");
        bt1.preOrder();
        System.out.println("bt1中根遍历：");
        bt1.inOrder();
        System.out.println("bt1后根遍历：");
        bt1.postOrder();
        
        // 根据未表名空子树的先根和中根次序来构造二叉树
        System.out.println("测试BinaryTree(T[] prelist, T[] inlist)：");
        String[] prelist = {"A", "B", "D", "G", "C", "E", "F", "H"};
        String[] inlist = {"D", "G", "B", "A", "E", "C", "H", "F"};
        BinaryTree<String> bt2 = new BinaryTree<String>(prelist, inlist);
        System.out.println("bt2先根遍历：");
        bt2.preOrder();
        System.out.println("bt2中根遍历：");
        bt2.inOrder();
        
        // 根据表明空子树的先根次序构造二叉树
        System.out.println("测试BinaryTree(T[] prelist)：");
        String[] prelist1 = {"A", "B", "D", null, "G", null, null, null, "C", "E", null, null, "F", "H", null, null, null};
        BinaryTree<String> bt3 = new BinaryTree<String>(prelist1);
        System.out.println("bt3先根遍历：");
        bt3.preOrder();
        System.out.println("bt3中根遍历：");
        bt3.inOrder();
        
        // 深拷贝构造二叉树
        System.out.println("测试BinaryTree(BinaryTree<T> tree)：");
        BinaryTree<String> bt4 = new BinaryTree<String>(bt2);
        System.out.println("bt4先根遍历：");
        bt4.preOrder();
        System.out.println("bt4中根遍历：");
        bt4.inOrder();
        
        // 层序遍历二叉树
        System.out.println("测试levelorder()：");
        bt4.levelOrder();
        
        // 返回二叉树的广义表表示字符串
        System.out.println("测试toGenString(BinaryNode<T> p)：");
        System.out.println(bt3.toGenListString());
        
        // 先序遍历二叉树用栈实现
        System.out.println("测试preOrderTraverse()：");
        bt3.preOrderTraverse();

        // 返回二叉树的结点数
        System.out.println("测试size()：");
        System.out.println(bt3.size());
        
        // 返回二叉树的高度
        System.out.println("测试height()：");
        System.out.println(bt3.height());
        
        // 查找并返回首个与key相等元素结点
        System.out.println("测试search(T key)：");
        System.out.println(bt3.search("F"));
        
        // 返回首个与key相等元素结点所在层次
        System.out.println("测试level(T key)：");
        System.out.println(bt3.level("F"));
        
        // 查找并删除首个以与key相等元素为根的子树
        System.out.println("测试remove(T key)：");
        System.out.println(bt3.toGenListString());
        bt3.remove("C");
        System.out.println(bt3.toGenListString());
        
        // 返回以层序遍历序列levelList构造完全二叉树
        System.out.println("测试createComplete(T[] levelList)：");
        String[] levelList = {"A", "B", "C", "D", "E", "F"};
        System.out.println(createComplete(levelList).toGenListString());
    }

}
